﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Diagnostics.Contracts;

namespace RgnAnalyzer.Domain
{
	/// <summary>
	/// This class implements a number of static methods for efficiently dealing with lists of unique sorted values.
	/// </summary>
	internal static class UniqueSortedArray
	{
		/////////////////////////////////////////////////////////////
		//Specialize for integer arrays

		/// <summary>
		/// Make a unique sorted array of integers.
		/// </summary>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
		public static int[] MakeIntArray(ICollection<int> c)
		{
			Contract.Ensures(IsUniqueSortedArray<int>(Contract.Result<int[]>()));

			int[] res = c.ToArray<int>();
			Array.Sort(res);
			return res;
		}

		/// <summary>
		/// Return true if the unique sorted array contains the given value (specialized for integers).
		/// </summary>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
		public static bool IntArrayContains(int v, int[] a)
		{
			if(a.Length < 8)
			{
				for(int i = 0; i < a.Length; ++i)
				{
					if(a[i] == v)
						return true;
				}

				return false;
			}
			else
				return Array.BinarySearch<int>(a, v) >= 0; 
		}

		/// <summary>
		/// Return true if the two unique sorted arrays overlap, (on any values after the given index and specialized for integers).
		/// </summary>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
		public static bool IntArraysOverlap(int[] a1, int[] a2)
		{
			int v1, v2;
			int index1 = 0;
			int index2 = 0;
			while((index1 < a1.Length) & (index2 < a2.Length))
			{
				v1 = a1[index1];
				v2 = a2[index2];

				if(v1 == v2)
					return true;
				else if(v1 < v2)
					++index1;
				else
					++index2;
			}

			return false;
		}

		/// <summary>
		/// Return true if the two unique sorted arrays are equal (specialized for integers).
		/// </summary>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
		public static bool IntArrayEquals(int[] a1, int[] a2)
		{
			if(a1.Length != a2.Length)
				return false;

			for(int i = 0; i < a1.Length; ++i)
			{
				if(a1[i] != a2[i])
					return false;
			}

			return true;
		}

		/////////////////////////////////////////////////////////////
		//Specialize for pointer arrays

		/// <summary>
		/// Make a unique sorted array of the given type.
		/// </summary>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
		public static T[] MakeArray<T>(ICollection<T> c) where T : IComparable<T>
		{
			Contract.Ensures(IsUniqueSortedArray<T>(Contract.Result<T[]>()));

			T[] res = c.ToArray<T>();
			Array.Sort(res);
			return res;
		}

		/// <summary>
		/// Return true if the unique sorted array contains the given value.
		/// </summary>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
		public static bool ArrayContains<T>(T v, T[] a) where T : class, IComparable<T>
		{
			if(a.Length < 8)
			{
				for(int i = 0; i < a.Length; ++i)
				{
					if(a[i] == v)
						return true;
				}

				return false;
			}
			else
			return Array.BinarySearch<T>(a, v) >= 0; 
		}

		/// <summary>
		/// Return true if the two unique sorted arrays overlap.
		/// </summary>
		public static bool ArraysOverlap<T>(T[] a1, T[] a2) where T : class, IComparable<T>
		{
			T v1, v2;
			int index1 = 0;
			int index2 = 0;
			while((index1 < a1.Length) & (index2 < a2.Length))
			{
				v1 = a1[index1];
				v2 = a2[index2];

				if(v1 == v2)
					return true;
				else if(v1.CompareTo(v2) < 0)
					++index1;
				else
					++index2;
			}

			return false;
		}

		/// <summary>
		/// Return true if the two unique sorted arrays are equal.
		/// </summary>
		public static bool ArrayEquals<T>(T[] a1, T[] a2) where T : IEquatable<T>
		{
			if(a1.Length != a2.Length)
				return false;

			for(int i = 0; i < a1.Length; ++i)
			{
				if(!(a1[i].Equals(a2[i])))
					return false;
			}

			return true;
		}

		/// <summary>
		/// Return true if the two unique sorted arrays are setwise <c>sub</c> is a subset of <c>into</c>.
		/// </summary>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
		public static bool ArraySubset<T>(T[] sub, T[] into) where T : IComparable<T>
		{
			if(sub.Length > into.Length)
				return false;

			T v1, v2;
			int index1 = 0;
			int index2 = 0;
			while((index1 < sub.Length) & (index2 < into.Length))
			{
				v1 = sub[index1];
				v2 = sub[index2];

				int cmpto = v1.CompareTo(v2);
				if(cmpto > 0)
					return false;

				if(cmpto <= 0)
					++index1;

				if(cmpto == 0)
					++index2;
			}

			return index1 == sub.Length;
		}

		/////////////////////////////////////////////////////////////
		//General helper code

		/// <summary>
		/// Returns true if the given array is unique and sorted.
		/// </summary>
		[Pure]
		public static bool IsUniqueSortedArray<T>(T[] arr) where T : IComparable<T>
		{
#if DEBUG
			for(int i = 1; i < arr.Length; ++i)
			{
				if(arr[i - 1].CompareTo(arr[i]) >= 0)
					return false;
			}

			return true;
#else
			return true;
#endif
		}

		/// <summary>
		/// Returns true if the given array is unique and sorted.
		/// </summary>
		[Pure]
		public static bool IsUniqueSortedList<T>(List<T> l) where T : IComparable<T>
		{
#if DEBUG
			for(int i = 1; i < l.Count; ++i)
			{
				if(l[i - 1].CompareTo(l[i]) >= 0)
				{
					int c1 = l[i - 1].CompareTo(l[i]);
					int c2 = l[i].CompareTo(l[i - 1]);

					return false;
				}
			}

			return true;
#else
			return true;
#endif
		}
	}
}
